﻿#define _CRT_SECURE_NO_WARNINGS

//// 枚举值表示颜色
//enum Colour
//
//{
//	RED,
//	BLACK
//};
//
//// 这⾥我们默认按key/value结构实现 
//
//template<class K, class V>
//
//struct RBTreeNode
//
//{
//	// 这里更新控制平衡也要加⼊parent指针 
//	pair<K, V> _kv;
//	RBTreeNode<K, V>* _left;
//	RBTreeNode<K, V>* _right;
//	RBTreeNode<K, V>* _parent;
//	Colour _col;
//	RBTreeNode(const pair<K, V>& kv)
//		:_kv(kv)
//		, _left(nullptr)
//		, _right(nullptr)
//		, _parent(nullptr)
//	{}
//};
//
//template<class K, class V>
//
//class RBTree
//{
//	typedef RBTreeNode<K, V> Node;
//
//public:
//
//private:
//	Node* _root = nullptr;
//};


////	g
//// p u
////父节点在组父节点左边
//if (parent == grandfather->_left)
//{
//	Node* uncle = grandfather->_right;
//	if (uncle && uncle->_col == RED)
//	{
//		// u存在且为红 ->变⾊再继续往上处理 
//		parent->_col = uncle->_col = BLACK;
//		grandfather->_col = RED;
//		cur = grandfather;
//		parent = cur->_parent;
//	}
//
//}
//
////	g
//// u p
////父节点在组父节点右边
//else
//{
//	Node* uncle = grandfather->_left;
//	// u存在且为红 ->变⾊再继续往上处理 
//	if (uncle && uncle->_col == RED)
//	{
//		parent->_col = uncle->_col = BLACK;
//		grandfather->_col = RED;
//		// 继续往上处理 
//		cur = grandfather;
//		parent = cur->_parent;
//	}
//	else
//	{
//		//第二种调整情况
//		//...
//	}
//}

// 父节点在组父节点左边
// u存在且为黑或不存在 -> 旋转+变⾊ 
if (cur == parent->_left)
{
	//  g
	// p u
	//c
	//单旋 
	RotateR(grandfather);

	parent->_col = BLACK;
	grandfather->_col = RED;
}

else
{
	//  g
	// p u
	//  c
	//双旋 
	RotateL(parent);
	RotateR(grandfather);

	cur->_col = BLACK;
	grandfather->_col = RED;
}

// 父节点在组父节点右边
// u存在且为黑或不存在 -> 旋转+变⾊ 
else
{
	//  g
	// u p
	//    c
	// 单旋
	if (cur == parent->_right)
	{
		RotateL(grandfather);

		parent->_col = BLACK;
		grandfather->_col = RED;
	}
	else
	{
		//  g
		// u p
		//  c
		// 双旋
		RotateR(parent);
		RotateL(grandfather);

		cur->_col = BLACK;
		grandfather->_col = RED;
	}
}